<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,200分)- 最小传输时延Ⅱ（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>有M*N的节点矩阵&#xff0c;每个节点可以向8个方向&#xff08;上、下、左、右及四个斜线方向&#xff09;转发数据包&#xff0c;每个节点转发时会消耗固定时延&#xff0c;连续两个相同时延可以减少一个时延值&#xff08;即当有K个相同时延的节点连续转发时可以减少K- 1个时延值&#xff09;&#xff0c;</p> 
<p>求左上角&#xff08;0&#xff0c;0&#xff09;开始转发数据包到右下角&#xff08;M-1&#xff0c;N- 1&#xff09;并转发出的最短时延。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第一行两个数字&#xff0c;M、N&#xff0c;接下来有M行&#xff0c;每行有N个数据&#xff0c;表示M* N的矩阵。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>最短时延值。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">3 3<br /> 0 2 2<br /> 1 2 1<br /> 2 2 1</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">3</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">3 3<br /> 2 2 2<br /> 2 2 2<br /> 2 2 2</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">4</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">&#xff08;2 &#43; 2 &#43; 2 -&#xff08;3-1))</td></tr></tbody></table> 
<p> </p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题是求两点之间的最短路径。</p> 
<p></p> 
<p>对于最短路径问题&#xff0c;最简单的求解思路就是BFS&#xff0c;但是BFS只适用于处理无权图的最短路径。</p> 
<blockquote> 
 <p>所谓无权图&#xff0c;即图中各顶点之间的边没有权重&#xff0c;或者可以理解为各相连顶点之间距离相同。</p> 
</blockquote> 
<p></p> 
<p>对于有权图的最短路径求解&#xff0c;有多种解题思路&#xff0c;比如Dijkstra&#xff0c;Floyed&#xff0c;Bellma-ford&#xff0c;SPFA。</p> 
<p>本题将使用SPFA算法来求解最短路径。</p> 
<blockquote> 
 <p>所谓SPFA算法&#xff0c;其实就是对无权图的BFS算法的优化。</p> 
 <ul><li>在无权图的BFS扩散过程中&#xff0c;最先碰到终点的路径<span style="color:#fe2c24;"> 一定是</span> 最短路径&#xff0c;因为这条路径从起点到终点经历的节点数最少&#xff0c;而无权图中&#xff0c;相连节点之间的距离是相同的&#xff0c;因此路径中节点数越少&#xff0c;距离就越短。</li><li>在有权图中的BFS扩散过程中&#xff0c;最先碰到终点的路径 <span style="color:#fe2c24;">不一定是</span> 最短路径&#xff0c;此时各节点之间的距离是不同的&#xff0c;因此节点数少&#xff0c;不能代表路径就短。</li></ul> 
</blockquote> 
<p></p> 
<p>关于SPFA算法可以看下这个视频讲解&#xff1a;</p> 
<p><a href="https://www.bilibili.com/video/BV1RK4y1d7ct?p&#61;4&amp;vd_source&#61;b5105a99a0628dd906e154263279c518" rel="nofollow" title="SPFA算法_哔哩哔哩_bilibili">SPFA算法_哔哩哔哩_bilibili</a></p> 
<p>后面有时间会补充一篇博客。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

void (async function () {
  // 地图矩阵行数,列数
  const [m, n] &#61; (await readline()).split(&#34; &#34;).map(Number);

  // 地图矩阵
  const matrix &#61; [];

  // 最短路径矩阵&#xff0c;即dist[i][j]记录的是坐标(i,j)到(0,0)的最短距离
  // 最短路径矩阵初始化&#xff0c;假设每个点到(0,0)距离无穷大
  const dist &#61; new Array(m).fill(0).map(() &#61;&gt; new Array(n).fill(Infinity));

  for (let i &#61; 0; i &lt; m; i&#43;&#43;) {
    matrix.push((await readline()).split(&#34; &#34;).map(Number));
  }

  console.log(spfa(matrix, dist, m, n));
})();

// 八个方向偏移量
const offsets &#61; [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
  [-1, -1],
  [-1, 1],
  [1, -1],
  [1, 1],
];

// 最短路径算法
function spfa(matrix, dist, m, n) {
  const queue &#61; [[0, 0]];
  dist[0][0] &#61; matrix[0][0];

  while (queue.length &gt; 0) {
    const [x, y] &#61; queue.shift();

    for (let [offsetX, offsetY] of offsets) {
      const newX &#61; x &#43; offsetX;
      const newY &#61; y &#43; offsetY;

      if (newX &gt;&#61; 0 &amp;&amp; newX &lt; m &amp;&amp; newY &gt;&#61; 0 &amp;&amp; newY &lt; n) {
        let newDist &#61; dist[x][y] &#43; matrix[newX][newY];

        // 题目说&#xff1a;连续两个相同时延可以减少一个时延值
        // 但是需要注意的是&#xff0c;应该不能产生负的时延值&#xff0c;比如前一个时延是0&#xff0c;当前时延也是0&#xff0c;则减少1个时延值&#xff0c;不应该变为-1
        if (matrix[newX][newY] &#61;&#61; matrix[x][y] &amp;&amp; matrix[x][y] &gt;&#61; 1) {
          newDist -&#61; 1;
        }

        if (newDist &lt; dist[newX][newY]) {
          dist[newX][newY] &#61; newDist;
          queue.push([newX, newY]);
        }
      }
    }
  }

  return dist[m - 1][n - 1];
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  // 地图矩阵
  static int[][] matrix;

  // 最短路径矩阵&#xff0c;即dist[i][j]记录的是坐标(i,j)到(0,0)的最短距离
  static int[][] dist;

  // 地图矩阵行数
  static int m;
  // 地图矩阵列数
  static int n;

  // 八个方向偏移量
  static int[][] offsets &#61; {<!-- -->{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    m &#61; sc.nextInt();
    n &#61; sc.nextInt();

    matrix &#61; new int[m][n];
    dist &#61; new int[m][n];
    for (int i &#61; 0; i &lt; m; i&#43;&#43;) {
      for (int j &#61; 0; j &lt; n; j&#43;&#43;) {
        matrix[i][j] &#61; sc.nextInt();
        // 最短路径矩阵初始化&#xff0c;假设每个点到(0,0)距离无穷大
        dist[i][j] &#61; Integer.MAX_VALUE;
      }
    }

    System.out.println(spfa());
  }

  public static int spfa() {
    LinkedList&lt;int[]&gt; queue &#61; new LinkedList&lt;&gt;();
    queue.add(new int[] {0, 0});
    dist[0][0] &#61; matrix[0][0];

    while (queue.size() &gt; 0) {
      int[] tmp &#61; queue.removeFirst();
      int x &#61; tmp[0], y &#61; tmp[1];

      for (int[] offset : offsets) {
        int newX &#61; x &#43; offset[0];
        int newY &#61; y &#43; offset[1];

        if (newX &gt;&#61; 0 &amp;&amp; newX &lt; m &amp;&amp; newY &gt;&#61; 0 &amp;&amp; newY &lt; n) {
          int newDist &#61; dist[x][y] &#43; matrix[newX][newY];

          // 题目说&#xff1a;连续两个相同时延可以减少一个时延值
          // 但是需要注意的是&#xff0c;应该不能产生负的时延值&#xff0c;比如前一个时延是0&#xff0c;当前时延也是0&#xff0c;则减少1个时延值&#xff0c;不应该变为-1
          if (matrix[newX][newY] &#61;&#61; matrix[x][y] &amp;&amp; matrix[newX][newY] &gt;&#61; 1) {
            newDist -&#61; 1;
          }

          if (newDist &lt; dist[newX][newY]) {
            dist[newX][newY] &#61; newDist;
            queue.add(new int[] {newX, newY});
          }
        }
      }
    }

    return dist[m - 1][n - 1];
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python">import sys

# 输入获取
m, n &#61; map(int, input().split())
matrix &#61; [list(map(int, input().split())) for i in range(m)]

# 最短距离矩阵
dist &#61; [[sys.maxsize for _ in range(n)] for _ in range(m)]

# 八个方向的偏移量
offsets &#61; ((-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1))


# 算法入口
def spfa():
    queue &#61; [[0, 0]]
    dist[0][0] &#61; matrix[0][0]

    while len(queue) &gt; 0:
        x, y &#61; queue.pop(0)

        for offsetX, offsetY in offsets:
            newX &#61; x &#43; offsetX
            newY &#61; y &#43; offsetY

            if m &gt; newX &gt;&#61; 0 and n &gt; newY &gt;&#61; 0:
                newDist &#61; dist[x][y] &#43; matrix[newX][newY]

                if matrix[newX][newY] &#61;&#61; matrix[x][y] and matrix[newX][newY] &gt;&#61; 1:
                    newDist -&#61; 1

                if newDist &lt; dist[newX][newY]:
                    dist[newX][newY] &#61; newDist
                    queue.append([newX, newY])

    return dist[m-1][n-1]


# 算法调用
print(spfa())
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>